/**
 * @author cookie
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

let nums = [1, 0, -1, 11, 89, -98, 10, 34, -56, 56]


/**
 * 方法一: 
 *          三层循环, 问每个数, 适合的拿出来. 
 *          但是这样的时间复杂度为O(n**3), n的立方. 
 * 
 */


/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeNums = function (nums) {
    if (nums.length <= 1) return [];
    let res = []
    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let z = j + 1; z < nums.length; z++) {
                if (nums[i] + nums[j] + nums[z] === 0) {
                    res.push([i, j, z])
                }
            }
        }
    }
    return res;
}

const res = threeNums(nums)
console.log(res);


/**
 * 方法2: 
 *          两层层循环, 先找到两个数, 然后, 使用map获取第三个数
 *          但是这样的时间复杂度为O(n**2), n的平方. 
 * 
 */

// const threeSum = function (nums) {
//     if (nums.length <= 1) return [];
//     let res = []
//     let newMap = new Map()
//     for (let i = 0; i < nums.length - 2; i++) {
//         for (let j = i + 1; j < nums.length - 1; j++) {
//             //    找两个数, 然后, 第三个数存在map里面
//             const rest = 0 - nums[i] - nums[j]
//             if (newMap.has(rest)) {
//                 res.push([newMap.get(rest), i, j])
//             } else {
//                 newMap.set(nums[i], i)
//                 newMap.set(nums[j], j)
//             }
//         }
//     }
//     return res;
// }

// const result = threeSum(nums)
// console.log(result);


function T(num, target) {
    let res = []
    for(let i = 0; i< num.length; i++) {
        let left = i +1, right = num.length -1
        while(left < right) {
            if(num[i] + num[left] +num[right] ===  target) {
                res.push(num[i], num[left], num[right])
                while(left < right && num[left] === num[left + 1 ]) left++
                while(left < right && num[right] === num[right-1]) right--
                i++
                j--
            }else if(num[i] + num[left] +num[right] < target ){
                left ++
            }else {
                right--
            }
        }
    }
    return res;
}